/*
 * @lc app=leetcode.cn id=1074 lang=typescript
 *
 * [1074] 元素和为目标值的子矩阵数量
 */

// @lc code=start
function numSubmatrixSumTarget(matrix: number[][], target: number): number {
  const m = matrix.length;
  const n = matrix[0].length;

  // 计算当前前缀和中是否有符合条件的元素
  const calcCount = (sum: number[], target: number): number => {
    let count = 0;
    let prefixSum = 0;
    const hash = new Map([[0, 1]]);

    for (const x of sum) {
      // 二维前缀和
      prefixSum += x;
      if (hash.has(prefixSum - target)) count += hash.get(prefixSum - target);
      hash.set(prefixSum, (hash.get(prefixSum) || 0) + 1);
    }
    return count;
  };

  let result = 0;
  for (let i = 0; i < m; i++) {
    const sum = new Array(n).fill(0);
    for (let j = i; j < m; j++) {
      for (let k = 0; k < n; k++) {
        // 计算同列元素的累加结果
        sum[k] += matrix[j][k];
      }
      // 每次枚举下边界后，去计算当前子矩阵内有多少结果
      result += calcCount(sum, target);
    }
  }

  return result;
}
// @lc code=end
